#ifndef __MERGESORT__
#define __MERGESORT__
#include "SortTool.h"
#define STABLE 1
#define LINKED 0

//标准版的mergesort 是具有稳定性的，其效率为O（NlgN）
//mergesort 与输入文件的顺序是无关的，只于其数量有关。（某种意义上的缺陷）
//执行过程是顺序访问，因此也比较适合用链表排序（还不用额外的辅助空间）
//比quicksort 通常意义上要慢一点

//值得注意的是：循环内的前2个if 判断在大多数的时间里是无效的
//可以给数组的尾部添加标志信息来减少这种判断(通常很难实现)
//或者牺牲稳定性，采用bitonic 序列的aux 数组进行排序，参见non-stable 版本
#if STABLE
template <class item>
void merge(item arr[], int left, int mid, int right){
	static item aux[MAX_ARRAY_NUM];
	int pre_len = mid - left+1,
		post_len = right - mid,
		i = left, j = mid+1,
		pre_cnt = 0, post_cnt = 0;
	for(int k = left; k <= right; ++k){
		if(pre_cnt == pre_len) { aux[k] = arr[j++]; continue;}
		if(post_cnt == post_len) { aux[k] = arr[i++]; continue;}
		if(arr[i] < arr[j]) { aux[k] = arr[i++]; ++pre_cnt;}
		else {aux[k] = arr[j++]; ++post_cnt;}
	}
	for(int i = left; i <= right; ++i) 	arr[i] = aux[i];
}
#else
template <class item>
void merge(item arr[], int left, int mid, int right){
	static item aux[MAX_ARRAY_NUM];
	int i;
	for(i = left; i <= mid; ++i) aux[i] = arr[i];
	for(int j = right; j >= mid+1; --j) aux[i++] = arr[j];
	int j = left; --i;
	for(int k = left; k <= right; ++k){
		if(aux[j] < aux[i]) arr[k] = aux[j++];
		else arr[k] = aux[i--];
	}
}
#endif
#if LINKED
template <class item>
struct item{
	item value;
	item* next;
	item(int v):value(v),next(NULL){}
};


template <class item>
item* merge(item* left, item* right){
	item dummy(0); item* head = &dummy, c = head;
	while(left != 0 && right !=0)
		if(left->value < right->value){
			c->next = left; c = left; left = left->next;
		}else{
			c->next = right; c = right; right = right->next;
		}
	c->next = (left == 0 ? right : left);
	return head->next;
}

template <class item>
item* mergesort(item* arra){
	if(arr == NULL || arr->next == NULL) return arr;
	item* a = arr , b = arr->next;
	for(;;){
		if(b == NULL || b->next == NULL) break;
		arr = arr->next; b = b->next->next;
	}
	b = arr->next; arr->next = NULL;
	merge(mergesort(a), mergesort(b));
}
#else
template <class item>
void mergesort(item arr[], int left, int right){
	if(arr == NULL || left >= right) return;
	int mid = (right + left) / 2;
	mergesort(arr, left, mid);
	mergesort(arr, mid+1, right);
	merge(arr, left, mid, right);
}
#endif

#endif